//只要找到两边高中间低的部分，就可以接雨水
//维护一个非递增的栈
//如果height[i]大于栈顶元素，就说明右边的高找到了
    //此时出栈，栈顶元素就是左边的高
    //左边的高和底处高度相等，就说明该处不能接水
    //继续出栈，直到栈为空或找到高墙
class Solution {
public:
    int trap(vector<int>& height) {
        int ret = 0, n = height.size();
        stack<int> myStack;

        for (int i = 0; i < n; i++)
        {
            while (!myStack.empty() && height[i] > height[myStack.top()])
            {
                int top_index = myStack.top();
                myStack.pop();
                if (myStack.empty())    //左边没墙了
                    break;

                int topHigh = height[top_index];
                int left = myStack.top();
                int width = i - left - 1;   //两边板子夹着的宽度

                //水桶原理
                //可以盛水的高度应该是 左右两边的地处 - 底部高度
                int high = min(height[left], height[i]) - topHigh;
                ret += width * high;
            }
            myStack.push(i);
        }

        return ret;
    }
};